It is desirable to describe mechanical parts and assemblies, when using computer-aided design systems, not merely in terms of numeric requirements like angles and dimensions, but also in terms of geometric requirements. For example, specified faces are to be parallel, circles and lines are to be tangent, or edges are to meet at a specified vertex. By combining such geometric requirements with symbolic numerical requirements, a model can be defined that will generate many different but related physical shapes, as controlled by values of the symbolic constraint parameters, and that will serve as a template for mating shapes in an assembly. The use of geometric information to specify shapes of physical objects is "construction geometry." The combination of geometric and numeric requirements is "geometric constraints."
Combining geometric requirements with numeric requirements often fails to describe shapes of physical objects completely. For example, any asymmetric object has a mirror image with exactly the same geometric elements, the same geometric relations, and the same numerical properties. The differences between an asymmetric shape and its mirror image are topological properties. One object may have a notch to the left of center, the other to the right. For many practical mechanical designs, geometric constraint systems need to be augmented using topological properties, in order to describe shapes completely. Topological properties may be identified although not specified, they may be specified explicitly, they may be specified through the topology exhibited in an approximate configuration of the geometric elements, they may be specified by reference to other geometric objects, or they may be specified in a combination of ways. A collection of geometric and numeric requirements for geometric elements augmented using topological properties is a "topological constraint system."
Sometimes, a designer may need to examine a partial solution to a topological constraint system before completing a definition for all constraints. In other circumstances, a designer may want to move or distort selected geometric elements of a topological constraint system or to explore spatial relations among them or with other geometry. A designer may also make a mistake, adding an inconsistent constraint; and the designer may want to see a solution up to the point of error, in order to correct the problem. To meet these needs, a method for solving a topological constraint system should be fast and robust.
Several methods are known for solving systems of constraints. Some methods represent constraints as equations; they may provide choices among multiple roots of equations, but they are unable to identify the topological significance of the choices. So-called "propagational" or "parametric" numerical methods may recognize topological properties but can find their progress blocked by coupled constraints that cannot be solved individually. So-called "variational" methods typically solve coupled constraints, but they are relatively slow, they encounter accuracy and stability problems, and they often fail to converge when there is a singularity in the topological constraint system. U.S. Pat. No. 5,043,929 and U.S. patent application 07/365,586 disclose certain techniques for solving constraint systems using degrees of freedom analysis that can overcome such problems, but they primarily address constraint systems for geometry of kinematic mechanisms rather than for construction geometry, and they do not explicitly recognize topological properties or means for satisfying topological requirements.
In "Reasoning about Geometric Constraints" (1989), Arbab and Wang describe "Operational Transformation Planning" (OTP), an approach to solving constraint systems based upon planning sequences of operations (e.g., rotations and translations). OTP does not recognize topological properties or topological requirements. OTP is also much less efficient than degrees of freedom analysis because it requires that a constraint be solved repeatedly as additional constraints are solved. In addition, to solve many constraint systems OTP must backtrack, i.e., throw away part of its solution and start over. Finally, the operational transformation component of OTP cannot solve constraint systems with simple cycles of constraints; instead, these cycles must be explicitly recognized and solved with numerical iteration techniques.
Aldefeld, in "Variation of geometries based on a geometric-reasoning method" (1988), describes an approach to geometric constraint satisfaction based upon constraint propagation rules. The rules used in this system are informally devised, based upon techniques of constructive geometry. An initial database of geometric entities and relationships (constraints) is created by the user. This method then applies its rules in a forward-chaining manner to derive new relationships between entities and, ultimately, values for the descriptive variables of each entity. The geometric-reasoning method does not recognize topological properties or topological requirements. With this technique, the size of the database may grow exponentially, resulting in poor performance.
In "A CAD system with declarative specification of shape" (1987), Sunde follows an approach similar to Aldefeld's but represents all derived relationships in terms of "CA-sets," which are sets of pairs of points whose relative orientation is fixed, and "CD-sets," which are sets of points where each point is a fixed distance from every other point in the set. Sunde's system has only line segments and two types of constraints: distance between endpoints, and angle between line segments. It does not recognize topological properties or topological requirements. Sunde does not explain how such an approach could be adapted to a larger variety of geometric entities and constraints.
Bruderlin, in "Constructing three-dimensional geometric objects defined by constraints" (1986), describes another rule-based method. In this approach, the database consists only of points, used to define the geometric entities. Construction rules are used in a backward-chaining manner to derive the locations of points. While this approach avoids uncontrolled growth in the size of the database, the solution of each constraint may require an arbitrarily large amount of inference. Because only fully evaluated geometry is stored in the database, the same inferences may be made repeatedly, resulting in poor performance. Bruderlin recognizes that some constraint systems have multiple solutions, which exhibit topological properties, but he does not describe how to determine or specify topological properties. Like Sunde, Bruderlin also fails to explain how his approach could be adapted to a larger variety of geometric entities and constraints.
In "PictureEditor" (1989), Kin, et al., describe an approach that can solve problems that can be created with ruler and compass constructions. PictureEditor uses a technique called "2-forest propagation," which works backwards from unknowns to knowns, solving two constraints at a time. PictureEditor recognizes multiple solutions to systems but does not distinguish them topologically, providing only methods of finding nearest positions. Degrees of freedom analysis can solve a much wider range of constraints. Unlike "2-forest propagation," it can properly identify and solve geometric singularities.
In "Programming interactions by constraints" (1989), Todd solves constraint systems by reformulating the constraints as algebraic equations and then using Groebner bases to solve the equations symbolically. Compared to degrees of freedom analysis, this method is slower. Because it deals with algebra instead of geometry, it cannot identify the geometric significance of singularities. Todd, like Owen, recognizes multiple solutions to equation systems; he describes a method to try alternate solution branches when one branch fails, but his methods do not identify the topological significance of these branches. In "Mathematica, a System for Doing Mathematics by Computer" Addison-Wesley (1986) Wolfram describes computer software that can solve sets of equations both symbolically and numerically. Although Mathematica is among the most capable equation-solving programs available, it is unable to provide symbolic solutions or stable numerical solutions for some geometric constraint systems of only moderate complexity.
Both Wolfram, in "Mathematica, a System for Doing Mathematics by Computer" and B. Stroustrup, in "The C++ Programming Language" (1986) describe languages appropriate for expressing algorithms usable with the present invention and executing them on a digital computer.